#include <stdlib.h>
#include <stdio.h>
#include "headers/queue_link.h"
#include "headers/stack_link.h"
#include "headers/graph.h"

//BFS时，不同值：初始为0，候选(没访问，但已入队列)为1，已访问为2
//DFS递归时，不同值：初始为0，已访问为1
//DFS非递归时，不同值：初始为0，候选(没访问，但已入栈)为1，已访问为2
static int *visited;
static int *dist;

//注意：
//1、BFS即广度优先遍历不能用递归实现！
//
//2、bfs,在遍历过程中，可以得到图中各节点到初始节点v的最短距离！
//
//3、存在这样的点(容易被忽视)：没有访问到(visited == 0)，但已入队列(候选),因此不用再次入队列！
//	 因为这样的点对遍历输出没有影响(若不需计算距离，可以不考虑这种点)，但对计算距离有影响！即，它的头节点变了！
//	 这样就能解释，为什么《算法导论》中实现BFS时采用了 color[] 来区分节点的状态了！
void bfs(ALGraph *const graph,int vid){
	Queue que;
	int nid,tmp,*ptm;;
	initQueue(&que,sizeof(int));

	enqueue(&que,&vid);	//将第一个节点入队列
	dist[vid] = 0;//第一个节点到自身的距离为0

	while(!is_empty(&que)){//队列不为空
		dequeue(&que,&nid);//出队列
		if(visited[nid] != 2){//还没有被访问过(0)，即，或者是还没入对列(0)，或者是已入队列(1)

			visited[nid] = 2;
			printf("(%d:%d)  ",nid,dist[nid]);

			int *res = get_neighbors(graph,nid);//返回的肯定是堆上分配的空间，因为栈空间无法引用到了！
			if(res != NULL){
				ptm = res;
				while((tmp=*ptm++)!=-1){
					if(visited[tmp] == 0){//邻居节点如果已经访问过了(2),或已入队列(1)，则不加入队列！
						enqueue(&que,&tmp);//将该节点的所有邻居节点 入队列
						dist[tmp]=dist[nid]+1;//新的距离 = prev节点的距离 + 1
						visited[tmp] = 1;
					}
				}

				free(res);//所以必须手动释放
				res = ptm = NULL;
			}
		}

	}
	dropQueue(&que);
}

//DFS的递归实现
//《算法导论》中用一个time变量记录了访问节点的过程，具体参考书！
void dfs_recurse(ALGraph *const graph,int vid){
	if(visited[vid] == 1){//该节点已访问过了
		return;
	}

	//访问该节点
	printf("%d ",vid);
	visited[vid]=1;

	//得到邻居节点
	int *res = get_neighbors(graph,vid),*ptm;
	int tmp;
	if(res != NULL){
		ptm = res;
		while((tmp=*ptm++)!=-1){
			if(visited[tmp] == 0){//未访问过
				dfs_recurse(graph,tmp);
			}
		}

		free(res);//所以必须手动释放
		res = ptm = NULL;
	}

}

//这个是DFS的非递归版
//注意：递归程序可读性好，但效率很低；所有的递归程序都可以用非递归算法来实现
//不过要借助 Stack(栈) 这种结构
void dfs(ALGraph *const graph,int vid){
	int pid;
	Stack stack;
	initStack(&stack,sizeof(int));

	push_stack_link(&stack,&vid);//将初始节点放入栈中
	while(!isEmpty_stack_link(&stack)){
		pop_stack_link(&stack,&pid);
		printf("%d ",pid);
		visited[vid] = 2;

		//将他的邻居节点加入到栈中!
		int *res = get_neighbors(graph,vid),*ptm;
		int tmp;
		if(res != NULL){
			ptm = res;
			while((tmp=*ptm++)!=-1){
				if(visited[tmp] == 0){//未访问过
					push_stack_link(&stack,&tmp);
					visited[tmp] = 1;
				}
			}

			free(res);//所以必须手动释放
			res = ptm = NULL;
		}
	}
	dropStack(&stack);
}

void visit_func(){
	ALGraph graph;
	init_graph(&graph,"data/graph.txt");
	visited = (int*)malloc(sizeof(int)*(graph.vexSize + 1));
	memset(visited,0,sizeof(int)*(graph.vexSize + 1));//清0

	dist = (int*)malloc(sizeof(int)*(graph.vexSize + 1));
	memset(dist,0,sizeof(int)*(graph.vexSize + 1));//清0

	//----------------------- bfs --------------------------------
	//遍历所有节点
	int i;
	for(i=1;i<=graph.vexSize;i++){
		if(visited[i]==0){
			bfs(&graph,i);//如果是非连通图，则必须能够访问到孤立点
		}
	}

	//----------------------- dfs --------------------------------
	memset(visited,0,sizeof(int)*(graph.vexSize + 1));
	for(i=1;i<=graph.vexSize;i++){
		if(visited[i]==0){
			dfs(&graph,i);//如果是非连通图，则必须能够访问到孤立点
//			或者 dfs_recurse(&graph,i);
		}
	}

	free(visited);
	free(dist);

	drop_graph(&graph);
}


void main_visit_graph(){
	visit_func();
}
